package Queue;

import java.util.Arrays;

/**
 *  题目 ：有序队列
 *  题目详述 ：
 *  给定一个字符串 s 和一个整数 k。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
 *  返回在应用上述步骤的任意数量的移动后，字典上最小的字符串。
 *
 */
public class OrderQueue {
    /**
     * 核心思想 ：
     * （1）当k = 1时，总共存在n种字符串排序方式，即只需要去获取字典最小的字符串
     * （2）当k > 1时，
     * 注意 ：
     * （1）由于能够构造出任意的字符串形式，即字典最小的字符串，等价于对于输入的字符串进行重排即可；
     * （2）compareTo() 方法用于按字典顺序比较两个字符串的大小，该比较是基于字符串各个字符的 Unicode 值。
     */
    public String orderlyQueue(String s, int k) {
        if(k == 1){
            // 定义初始化字符串，用来存储字典上最小的字符串；
            // 即，由于k = 1，后续总共存在n中字符串的排序方式（使用暴力法，比较每一个字符串，得出最优字符串）
            String SmallestStr = s;
            int length = s.length();
            /**
             *  注意 ：
             *      由于Java中String类型的字符串是不能够进行修改，
             *      ===> 所以需要将String类型的字符串转化为StringBuilder/StringBuffer类型，
             *           同时对于字符串进行删除和拼接操作；
             *
             * toString和new String区别 ：
             * （1）toString是调用的对象本身的，也就是继承或者重写的object.toString()方法，如果是byte[] b,那么返回的是b的内存地址。
             * （2）new String()是使用虚拟机默认的编码base返回对应的字符。
             */
            StringBuilder str = new StringBuilder(s);
            // 当k = 1时，总共只存在n中字符串排序方式；
            // 即，进行n次字符串比较即可（n 为字符串的长度）
            for(int i = 0 ; i < length ; i++){
                char index = str.charAt(0);// 即，获取字符串的首个字符
                str.deleteCharAt(0); // 即，删除字符串的首个字符
                str.append(index); // 即，将之前删除的字符串首个字符添加到字符串尾部
                if(str.toString().compareTo(SmallestStr) < 0){
                    // 即，当重新进行排序的字符串str与所保存的smallestStr字符串进行相比
                    // 若是str字符串在字典上小于 所保存的smallestStr，即刷新smallestStr的值
                    SmallestStr = str.toString();
                }
            }
            return SmallestStr;
        }
        else{
            // 将所需要去获取字典上最小的字符串，直接拆解成字符数组；
            char[] array = s.toCharArray();
            // 对于字符数组中的所有字符，进行升序排序；
            Arrays.sort(array);
            // 由于最后方法的返回值为String类型，即需要将字符数组重新转化为字符串；
            System.out.println(new String(array));
            System.out.println(array.toString());
            return new String(array);
        }
    }
    /**
     * 分析 ：
     * （1）空间复杂度 ：O（1）；
     * （2）时间复杂度 ：
     *  当 k = 1时，for循环中对于字符串进行比较操作，即时间复杂度为O（n * n）；
     *  当 k > 1时，由于直接对于整个字符串进行排序（能够获取到任意排序的字符串），时间复杂度为 O（n * log(n)）;
     */
}
